package com.cheung.leetcode.normal;

import java.util.ArrayList;
import java.util.List;

public class LC39 {

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtracking(result, 0, new ArrayList<>(), candidates, target);
        return result;
    }

    private static void backtracking(List<List<Integer>> result, int begin,
                                     List<Integer> path, int[] candidates, int target) {
        if (target < 0) {
            return;
        }

        if (target == 0) {
            // 这里要新new一个对象
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i < candidates.length; i++) {
            path.add(candidates[i]);
            backtracking(result, i, path, candidates, target - candidates[i]);
            path.remove(path.size() - 1);
        }

    }

    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;

        List<List<Integer>> lists = combinationSum(candidates, target);
        System.out.println(lists);

    }
}
